
typedef struct
{
	char str[MaxSize];
	int length;
}String;
int BFIndex(String S, int start, String T)
{
	int i = start, j = 0, v;

	while(i < S.length && j < T.length)
	{
		if(S.str[i] == T.str[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	if(j==T.length) 
		v = i -T.length;
	else 
		v = -1;
	return v;
}

void GetNext(String T, int next[])
{
	int j = 1, k = 0;
	next[0] = -1;
	next[1] = 0;
	while(j < T.length)
	{
		if(T.str[j] == T.str[k])
		{
			next[j+1] = k + 1;
			j++;
			k++;
		}
		else if(k == 0)
		{
			next[j+1] = 0;
			j++;
		}
		else
			k = next[k];
	}
}

int KMPIndex(String S, int start , String T, int next[])
{
	int i = start , j = 0, v;

	while(i < S.length && j < T.length)
	{
		if(S.str[i] == T.str[j])
		{
			i++;
			j++;
		}
		
		else if(j == 0) i++;
		else j = next[j];
	}

	if(j == T.length) v = i - T.length;
	else v = -1;
	return v;
}

int BFIndexC(String S, int start, String T)
{
	int i = start, j = 0, t = 0;

	while(i < S.length && j < T.length)
	{
		t++;
		if(S.str[i] == T.str[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	return t;
}


int KMPIndexC(String S, int start , String T, int next[])
{
	int i = start , j = 0,t = 0;

	while(i < S.length && j < T.length)
	{
		t++;
		if(S.str[i] == T.str[j])
		{
			i++;
			j++;
		}
		
		else if(j == 0) i++;
		else j = next[j];
	}

	return t;
}